﻿// 1003 最大独立集.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
/*
http://oj.daimayuan.top/course/14/problem/799


给你一张二分图，图中没有重边，你需要求出这张图中最大独立集包含的顶点个数。

最大独立集是指：在图中选出最多的点，满足他们两两之间没有边相连。

图用以下形式给出：

第一行输入两个整数 n,m
，表示图的顶点数和边数，顶点编号从 1 到 n。

接下来 m行，每行两个整数 x,y
，表示 x 和 y 之间有一条边。

输出一个数为最大独立集大小。

输入格式
第一行两个整数 n,m。

接下来 m 行，每行有两个整数，代表一条边。

输出格式
输出一个数表示答案。

样例输入
4 3
1 2
1 4
3 4
样例输出
2
数据规模
对于所有数据，保证 2≤n≤1000,0≤m≤10000,1≤x,y≤n,x≠y
*/


vector<int> edge[1001];
int n, m, c[1001], a[10001][2], n1, n2, v[1001], r[1001];
int b[1001];

bool find(int x) {
    b[x] = true;
    for(auto y :edge[x])
        if (!v[y] || (!b[v[y]] && find(v[y]))) {
            v[y] = x;
            return true;
        }
    return false;
}

int match() {
    int ans = 0;
    memset(v, 0, sizeof v);
    for (int i = 1; i <= n; i++) {
        memset(b, false, sizeof b);
        if (find(i))
            ++ans;
    }
    return ans;
}

void dfs(int x) {
    for(auto y:edge[x])
        if (!c[y]) {
            c[y] = 3 - c[x];
            dfs(y);
        }
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d",&a[i][0],&a[i][1]);
        edge[a[i][0]].push_back(a[i][1]);
        edge[a[i][1]].push_back(a[i][0]);
    }

    memset(c,0,sizeof c);
    for (int i = 1; i <= n; i++) {
        if (!c[i]) {
            c[i] = 1;
            dfs(i);
        }
    }
    n1 = n2 = 0;
    for (int i = 1; i <= n; i++)
        if (c[i] == 1)
            r[i] = ++n1;
        else
            r[i] = ++n2;
    for (int i = 1; i <= n; i++)
        edge[i].clear();
    for (int i = 1; i <= m; i++) {
        int x = a[i][0], y = a[i][1];
        if (c[x] == 1)
            edge[r[x]].push_back(r[y]);
        else
            edge[r[y]].push_back(r[x]);
    }
    printf("%d\n",n-match());

    return 0;
}

 